`
https://leetcode.cn/problems/count-number-of-ways-to-place-houses/
`

/**
 * @param {number} n
 * @return {number}
 */
var countHousePlacements = function (n) {
  // 其实只需要考虑一侧即可，因为两侧互不影响，一侧的结果的平方就是答案
  const MOD = BigInt(1e9 + 7)
  // dp[i] 表示从当前地块开始能有多少种放置情况
  const dp = new Array(n + 2).fill(0n)

  dp[n + 1] = 1n
  dp[n] = 2n

  for (let i = n - 1; i >= 1; i--) {
    dp[i] = (
      // 放房子
      dp[i + 2] +
      // 不放房子
      dp[i + 1]
    )
  }

  return Number((dp[1] * dp[1]) % MOD)
};